import java.util.*;

public class Solution301 {

    private boolean judgeIsMatch(String s){
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '('){
                deque.add(c);
            }
            else if(c == ')'){
                if(deque.isEmpty() || deque.pollLast() != '('){
                    return false;
                }
            }
        }
        return deque.isEmpty();
    }

    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        Set<String> strSet = new HashSet<>();
        strSet.add(s);
        while(true){
            for (String str : strSet) {
                if(judgeIsMatch(str)){
                    res.add(str);
                }
            }
            if(!res.isEmpty()){
                return res;
            }
            Set<String> nextStrSet = new HashSet<>();
            for (String str : strSet) {
                for (int i = 0; i < str.length(); i++) {
                    nextStrSet.add(str.substring(0, i) + str.substring(i + 1));
                }
            }
            strSet = nextStrSet;
        }
    }

    public static void main(String[] args) {
        Solution301 s = new Solution301();
        s.removeInvalidParentheses("()())()");
    }
}
